#!/usr/bin/env python
# -*- indent-tabs-mode: nil; tab-width: 4; coding: utf-8 -*-
# vi: set ts=4 sts=4 sw=4 set smarttab set expandtab
#http://www.careercup.com/question?id=14681714
#Facebook interview question
"""
Given a set {1,2,3,4,5...n} of n elements, write code that outputs all subsets of length k. For example, if n = 4 and k = 2, the output would be {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}
"""

def preint_subsets(n, k):
    arr = [i for i in range(1, n + 1)]
    existing = []
    print_sets(arr, existing, 0, k)


def print_sets(arr, existing, start_index, k):
    if k == 0:
        print existing
        return

    if start_index >= len(arr): return

    for i in range(start_index, len(arr)):
        existing.append(arr[i])
        print_sets(arr, existing, i + 1, k - 1)
        existing.pop()

preint_subsets(6, 4)

